import java.util.HashMap;
import java.util.Map;

public class FourSix {

    /**
     *输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
     * 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
     * @param n
     * @return
     */
    public static int countDigitOne(int n) {
        int ans = 0;
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        int temp_ans,temp_val;
        for(int i=1;i<=n;i++){
            temp_ans = 0;
            temp_val = i;
            while (temp_val>0){
                if (map.containsKey(temp_val)){
                    temp_ans += map.get(temp_val);
                    break;
                }
                if (temp_val%10==1){
                    temp_ans++;
                }
                temp_val = temp_val/10;
            }
            if (temp_ans!=0){
                ans+=temp_ans;
                map.put(i,temp_ans);
            }

        }
        return ans;

    }


    public static void main(String[] args) {
        countDigitOne(13);
    }
}
